package interview.alibaba;

/**
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @program: arithmetic-learning 给定一个n，求 [1,n] 这 n 个数字的排列组合有多少个。条件：相邻的两个数字的绝对值不能等于1.
 * @description:
 * @since
 */

import java.util.ArrayList;
import java.util.List;

public class PermutationAndCombination {
    private static int N = 4;
    private static List<List<Integer>> ans = new ArrayList<>();


    public static void main(String[] args) {

        boolean[] check = new boolean[N + 1];
        List<Integer> tmp = new ArrayList<>();
        trace(N, 0, check, tmp);
        ans.forEach(list -> System.out.println("main ==>" + list));
        System.out.println("ans size " + ans.size());
    }

    public static void trace(int n, int index, boolean[] check, List<Integer> list) {
        if (index == n) {
            ans.add(new ArrayList<>(list));
        } else {
            for (int i = 1; i <= n; ++i) {
                if (!check[i] && (list.size() == 0 || Math.abs(list.get(list.size() - 1) - i) != 1)) {
                    list.add(i);
                    check[i] = true;
                    trace(n, index + 1, check, list);
                    list.remove(list.size() - 1);
                    check[i] = false;
                }
            }
        }
    }
}
